Medium
Related Topics: Hash Table / Math / String
LeetCode Source

解題想法

LeetCode Hint: Problem is simpler to solve by working the string from back to front and using a map.

首先，我們先建立一個 Hash Table mp

在過程中，我們透過比較當前 mp[s[i]] 的值跟前面遍歷值 prev_val 之大小

• 若 prev_val > mp[s[i]]，則 res -= mp[s[i]]
• 反之，則 res += mp[s[i]]

不過重點是最後每遍歷一個值要儲存 prev_val = mp[s[i]]

Python

class Solution:
    def romanToInt(self, s: str) -> int:
        mp = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
        res = 0
        prev_value = 0  # To keep track of the value of the previous Roman numeral
        for i in range(len(s) - 1, -1, -1):
            if mp[s[i]] < prev_value:
                res -= mp[s[i]]
            else:
                res += mp[s[i]]
            prev_value = mp[s[i]]
        return res

C++

class Solution {
public:
    int romanToInt(string s) {
        unordered_map <char, int> mp = {{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}};
        int res = 0, prev_val = 0;
        for (int i = s.size()-1; i > -1; i--) {
            if (mp[s[i]] < prev_val)
                res -= mp[s[i]];
            else
                res += mp[s[i]];
            prev_val = mp[s[i]];
        }
        return res;
    }
};

這系列文被記錄在 Top Interview 150 Series